class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int length = 0;
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            length = Math.max(x, length);
            length = Math.max(y, length);
        }
        length++;
        graph = new ArrayList<>(length);
        visited = new boolean[length];
        hasCycle = false;
        for (int i = 0; i < length; i++) {
            graph.add(new ArrayList<>());
            visited[i] = false;
        }
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            addEdge(x, y);
            addEdge(y, x);
            // 需要从已加完边的点出发，从1开始的话，可能1相关的边还没有添加上
            dfs(x, -1);
            if (hasCycle) {
                return edge;
            }
        }
        return null;
    }
    private void dfs(int start, int father) {
        visited[start] = true;
        for (int next : graph.get(start)) {
            if (next == father) {
                continue;
            }
            if (visited[next]) {
                hasCycle = true;
            } else {
                dfs(next, start);
            }
        }
        visited[start] = false;
    }
    private void addEdge(int x, int y) {
        this.graph.get(x).add(y);
    }
    private List<List<Integer>> graph;
    private boolean[] visited;
    private boolean hasCycle;
}
